package problem210;

//210.课程表2
//https://leetcode.cn/problems/course-schedule-ii/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[] findOrder(int n, int[][] p) {
        int[] in = new int[n]; //入度表
        int[] ret = new int[n];
        int index = 0;
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i<n; i++) {
            list.add(new ArrayList<>());
        }
        for(int i = 0; i<p.length; i++) {
            int a = p[i][0], b = p[i][1]; // b->a 在学习a之前需要先学习b
            list.get(b).add(a);
            in[a] ++; //a的入度加一
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            if(in[i] == 0) queue.add(i);
        }
        while(!queue.isEmpty()) {
            int b = queue.poll();
            ret[index++] = b;
            for(int i = 0; i<list.get(b).size(); i++) {
                int a = list.get(b).get(i);
                if(--in[a] == 0) queue.add(a);
            }
        }
        for(int i = 0; i<n; i++) {
            if(in[i] != 0) return new int[0];
        }
        return ret;
    }
}